#include <iostream>
#include <map>
#include <string>
#include <vector>

namespace rbt {

/**
 * @brief 颜色
 *
 */
enum class COLOR {
  RED = 0,
  BLACK = 1,
};

/**
 * @brief 树节点
 *
 */
struct Node {
  std::int32_t key;
  std::string value;
  COLOR color;
  Node *left;
  Node *right;
  Node *parent;
  std::int16_t depth;

  Node(const std::int32_t key, const std::string value,
       const COLOR color = COLOR::RED) {
    this->key = key;
    this->value = value;
    this->color = color;
    this->left = nullptr;
    this->right = nullptr;
    this->parent = nullptr;
    this->depth = 0;
  }
};

class RBT final {
private:
  Node *root;

public:
  RBT(/* args */) : root(nullptr) {}
  ~RBT() {}

  /**
   * 左旋示例代码：
   *       P                   R
   *      / \                 / \
   *     L   R     ====>     P  RR
   *        / \             / \
   *       RL RR           L  RL
   * @param node 旋转支点
   */
  void rotateLeft(Node *node) {
    // R
    auto rchild = node->right;
    // P.right = RL
    node->right = rchild->left;
    // RL.parent = P;
    if (rchild->left) {
      rchild->left->parent = node;
    }
    // R.parent = P.parent
    rchild->parent = node->parent;
    // 根节点情况，
    if (!node->parent) {
      this->root = rchild;
    } else {
      if (node == node->parent->right) {
        // node 是父节点的右节点，
        node->parent->right = rchild;
      } else {
        // node 是父节点的左节点，
        node->parent->left = rchild;
      }
    }
    // R.left = P
    rchild->left = node;
    // P.parent = R;
    node->parent = rchild;
  }

  /**
   * 右旋示例代码：
   *       R                 P
   *      / \               / \
   *     P  RR   ====>     L   R
   *   /  \                   / \
   *  L   RL                 RL RR
   * @param node 旋转支点
   */
  void rotateRight(Node *node) {
    // P
    auto lchild = node->left;
    // R.left = RL ;
    node->left = lchild->right;
    // RL.parent = R
    if (lchild->right) {
      lchild->right->parent = node;
    }
    // P.parent = R.parent;
    lchild->parent = node->parent;
    // 根节点情况，
    if (!lchild->parent) {
      this->root = lchild;
    } else {
      if (node == node->parent->right) {
        // node 是父节点的右节点，
        node->parent->right = lchild;
      } else if (node == node->parent->left) {
        // node 是父节点的左节点
        node->parent->left = lchild;
      }
    }
    // P.right = R;
    lchild->right = node;
    // R.parent = P;
    node->parent = lchild;
  }

  void update(Node *old_node, Node *new_node) {
    *old_node = *new_node;
    // old_node->value = new_node->value;
    // old_node->left = new_node->left;
    // old_node->right = new_node->right;
    // old_node->parent = new_node->parent;
    // old_node->color = new_node->color;
  }

  /**
   * 插入key, value
   */
  void insert(const std::int32_t key, const std::string value) {
    if (this->root) {
      // 红黑树为非空场景
      Node *parent;
      Node *node = this->root;
      auto newNode = new Node(key, value, COLOR::RED);
      // 查找插入位置
      while (node) {
        parent = node;
        if (key == node->key) {
          // 场景二： 插入节点key已存在
          newNode->color = node->color;
          this->update(node, newNode);
          return;
        } else if (key < node->key) {
          node = node->left;
        } else {
          node = node->right;
        }
      }
      newNode->parent = parent;
      if (key < parent->key) {
        parent->left = newNode;
      } else {
        parent->right = newNode;
      }
      this->balanceInsertion(newNode);
    } else {
      // 场景一：红黑树为空树场景
      this->root = new Node(key, value, COLOR::BLACK);
    }
  }

  // 插入节点平衡修正
  void balanceInsertion(Node *node) {
    // 场景三：插入节点的父节点为黑色节点，无需修正
    while (node->parent != nullptr && node->parent->color == COLOR::RED) {
      Node *uncle = nullptr;
      // 父节点是祖父节点左节点
      if (node->parent == node->parent->parent->left) {
        uncle = node->parent->parent->right;
        // 场景四：叔叔节点为红色
        if (uncle != nullptr && uncle->color == COLOR::RED) {
          // 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
          node->parent->color = COLOR::BLACK;
          uncle->color = COLOR::BLACK;
          node->parent->parent->color = COLOR::RED;
          node = node->parent->parent;
          continue;
        }
        // 场景五：叔叔节点为空节点或者是黑色节点；
        // 场景5.2 插入节点是父节点的右节点，先进行左旋转换到场景5.1
        if (node == node->parent->right) {
          // 左旋之后，原插入节点的父节点变成新插入节点；
          node = node->parent;
          this->rotateLeft(node);
        }
        // 场景5.1 插入节点是父节点的左节点；
        // 父节点变成黑色、祖父节点变成红色
        node->parent->color = COLOR::BLACK;
        node->parent->parent->color = COLOR::RED;
        // 对祖父节点右旋
        this->rotateRight(node->parent->parent);
      } else {
        // 父节点是祖父节点右子节点
        uncle = node->parent->parent->left;
        // 场景四：叔叔节点为红色
        if (uncle != nullptr && uncle->color == COLOR::RED) {
          // 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
          node->parent->color = COLOR::BLACK;
          uncle->color = COLOR::BLACK;
          node->parent->parent->color = COLOR::RED;
          node = node->parent->parent;
          continue;
        }
        // 场景5->4 插入节点是父节点的左节点，先进行右旋转换到场景5->3
        if (node == node->parent->left) {
          // 右旋之后，原插入节点的父节点变成新插入节点；
          node = node->parent;
          this->rotateRight(node);
        }
        // 场景5->3插入节点是父节点的右节点；
        // 父节点变成黑色、祖父节点变成红色
        node->parent->color = COLOR::BLACK;
        node->parent->parent->color = COLOR::RED;
        // 对祖父节点左旋
        this->rotateLeft(node->parent->parent);
      }
    }
    this->root->color = COLOR::BLACK;
  }

  // 先序遍历
  void preOrderTraverse(Node *node) {
    if (nullptr != node) {
      this->cal_node_depth(node);
      this->preOrderTraverse(node->left);
      this->preOrderTraverse(node->right);
    }
  }

  // 计算高度
  /// ![图](https://img2018.cnblogs.com/blog/1523448/201907/1523448-20190716212515612-1703079491.png)
  void cal_node_depth_2(Node *node, int depth) {
    if (nullptr != node) {
      node->depth = depth;
      cal_node_depth_2(node->left, depth + 1);
      cal_node_depth_2(node->right, depth + 1);
    }
  }

  // 判断本地字节序
  static bool is_big_endian() {
    std::int16_t val = 0x0102;
    char *p = (char *)&val;
    char c1 = *p;
    char c2 = *(p + 1);
    if (c2 == 0x01 && c1 == 0x02) {
      return true;
    } else {
      return false;
    }
  }

  std::map<std::int16_t, std::vector<Node *>> list;

  // 计算深度
  void cal_node_depth(Node *node) {
    node->depth = 0;
    auto tmp = node;
    while (tmp->parent != nullptr) {
      node->depth++;
      tmp = tmp->parent;
    }
    auto iter = list.find(node->depth);
    if (iter == list.end()) {
      std::vector<Node *> v;
      v.push_back(node);
      list.insert(std::make_pair(node->depth, std::move(v)));
    } else {
      iter->second.push_back(node);
    }
  }

  /// 按照深度打印
  void print_for_test() {
    list.clear();
    preOrderTraverse(this->root);
    for (auto i = list.begin(); i != list.end(); i++) {
      std::vector<Node *> &v = i->second;
      for (size_t ii = 0; ii < v.size(); ii++) {
        print_node(v[ii]);
      }
      std::cout << std::endl;
    }
  }

  void print_node(Node *node) {
    // 根节点打印
    // 左节点
    // 右节点
    if (node->parent == nullptr) {
      std::cout << "[" << node->key << (node->color == COLOR::RED ? 'r' : 'b')
                << "]";
    } else {
      if (node->parent->left == node) {
        std::cout << '[' << node->key << (node->color == COLOR::RED ? 'r' : 'b')
                  << '|';
      } else {
        std::cout << node->key << (node->color == COLOR::RED ? 'r' : 'b')
                  << ']';
      }
    }
  }

  /**
   * 查找节点
   * @param key 节点key值
   */
  Node *search(const std::int32_t key) {
    Node *node = this->root;
    while (node) {
      if (key < node->key) {
        node = node->left;
      } else if (key > node->key) {
        node = node->right;
      } else if (key == node->key) {
        break;
      }
    }
    return node;
  }

  /**
   * 替换u节点，重置v节点
   * @param u 待删除节点
   * @param v 子节点
   */
  void replace(Node *u, Node *v) {
    if (!u->parent) {
      // u是根节点，设置v为根节点
      this->root = v;
    } else if (u == u->parent->left) {
      // 重置u的父节点的左节点
      u->parent->left = v;
    } else {
      // 重置u的父节点的右节点
      u->parent->right = v;
    }
    // 重置v的父节点
    if (v) {
      v->parent = u->parent;
    }
  }

  /**
   * 查找node节点的后继节点
   */
  Node *findSuccessor(Node *node) {
    while (node->left) {
      node = node->left;
    }
    return node;
  }

  /**
   * 删除节点
   * @param key 删除节点key值
   */
  void deleteNode(const std::int32_t key) {
    Node *node = search(key);
    if (!node) {
      return;
    }
    Node *fix = nullptr;
    COLOR color = node->color;
    if (!node->left) {
      //左节点为空值
      fix = node->right;
      this->replace(node, node->right);
    } else if (!node->right) {
      //右节点为空值
      fix = node->left;
      this->replace(node, node->left);
    } else {
      // 左右节点都不为空值
      Node *successor = this->findSuccessor(node->right);
      //替换节点的颜色
      color = successor->color;
      //后继节点只存在右节点或者两个nil子节点情况
      fix = successor->right;
      //如果后继节点是父节点的非直接子节点
      if (successor->parent != node) {
        this->replace(successor, successor->right);
        // if (successor->right) {
        successor->right = node->right;
        successor->right->parent = successor;
        // }
      }
      this->replace(node, successor);
      successor->color = node->color;
      // if (successor->left) {
      successor->left = node->left;
      successor->left->parent = successor;
      // }
    }
    if (color == COLOR::BLACK) {
      this->balanceDeletion(fix);
    }
  }
  /**
   * 删除节点平衡修正
   * @param node 节点
   */
  void balanceDeletion(Node *node) {
    if (nullptr == node) {
      return;
    }
    while (node != this->root && node->color == COLOR::BLACK) {
      // 节点是父节点的左子节点
      if (node == node->parent->left) {
        //兄弟节点
        Node *sibling = node->parent->right;
        if (sibling->color == COLOR::RED) {
          // 场景2->1:兄弟节点是红色
          // 兄弟节点设置为黑色
          sibling->color = COLOR::BLACK;
          //替换节点的父节点设置为红色
          node->parent->color = COLOR::RED;
          // 左旋
          this->rotateLeft(node->parent);
          sibling = node->parent->right;
        }
        if (sibling->left->color == COLOR::BLACK &&
            sibling->right->color == COLOR::BLACK) {
          // 场景2->4: 兄弟节点两个子节点都是黑色
          sibling->color = COLOR::RED;
          //再次以父节点为新节点作自平衡处理。
          node = node->parent;
          continue;
        } else if (sibling->left->color == COLOR::RED) {
          // 场景2->3: 兄弟节点的左子节点是黑色，转换到场景2->2->
          sibling->left->color = COLOR::BLACK;
          sibling->color = COLOR::RED;
          //对兄弟节点右旋
          this->rotateRight(sibling);
          sibling = node->parent->right;
        }
        if (sibling->right->color == COLOR::RED) {
          //场景2->2：兄弟节点的右节点是红色
          sibling->color = node->parent->color;
          node->parent->color = COLOR::BLACK;
          sibling->right->color = COLOR::BLACK;
          //对父节点左旋
          this->rotateLeft(node->parent);
          // 左旋之后，红黑树重新平衡
          node = this->root;
        }
      } else {
        //节点是父节点的左节点
        Node *sibling = node->parent->left;
        if (sibling->color == COLOR::RED) {
          // 场景 3->1：替换节点的兄弟节点是红色
          sibling->color = COLOR::BLACK;
          node->parent->color = COLOR::RED;
          this->rotateRight(node->parent);
          sibling = node->parent->left;
        }
        if (sibling->right->color == COLOR::BLACK &&
            sibling->left->color == COLOR::BLACK) {
          //场景3->4：替换节点的两个子节点都是黑色
          sibling->color = COLOR::RED;
          //再次以父节点为新节点作自平衡处理。
          node = node->parent;
          continue;
        } else if (sibling->right->color == COLOR::RED) {
          // 场景3->3:兄弟节点的右子节点是红色
          sibling->right->color = COLOR::BLACK;
          sibling->color = COLOR::RED;
          this->rotateLeft(sibling);
          sibling = node->parent->left;
        }
        if (sibling->left->color == COLOR::RED) {
          // 场景3->2：兄弟节点的左子节点是红色
          sibling->color = node->parent->color;
          node->parent->color = COLOR::BLACK;
          sibling->left->color = COLOR::BLACK;
          this->rotateRight(node->parent);
          node = this->root;
        }
      }
    }
    node->color = COLOR::BLACK;
  }

}; // namespace rbt

} // namespace rbt

void rbt_demo() {
  using namespace rbt;
  for (size_t i = 0; i < 8; i++) {
    RBT rbt_obj;
    rbt_obj.insert(1, "hello");
    rbt_obj.insert(2, "world");
    rbt_obj.insert(3, "zuo");
    rbt_obj.insert(4, "zuo");
    rbt_obj.insert(6, "zuo");
    rbt_obj.insert(5, "zuo");
    rbt_obj.insert(8, "zuo");
    rbt_obj.insert(7, "zuo");
    rbt_obj.print_for_test();
    std::cout << "------" << std::endl;
    // rbt_obj.deleteNode(6);
    // rbt_obj.deleteNode(7);
    // rbt_obj.deleteNode(8);
    // rbt_obj.deleteNode(5);
    // rbt_obj.deleteNode(4);
    // rbt_obj.deleteNode(2);
    // rbt_obj.deleteNode(3);
    // rbt_obj.deleteNode(1);
    rbt_obj.deleteNode(i);
    rbt_obj.print_for_test();
  }

  std::cout << "------" << std::endl;
}

void test_is_big_endian() {
  std::cout << rbt::RBT::is_big_endian() << std::endl;
}